package datastructure;

public class Trie {

	class Node {
		int next[], end;

		public Node() {
			next = new int[26];
			end = -1;
		}
	}

	Node[] node;

	String s;

	int size, cur;

	public Trie(int n) {
		node = new Node[n];
		node[1] = new Node();
		size = 2;
		cur = 0;
	}

	public void insert(String p) {
		s = p;
		insert(1, 0);
		cur++;
	}

	public int find(String p) {
		s = p;
		return find(1, 0);
	}

	private int find(int index, int pos) {
		if (index == 0)
			return -1;
		if (pos == s.length())
			return node[index].end;
		int next = node[index].next[s.charAt(pos) - 'a'];
		return find(next, pos + 1);
	}

	private void insert(int index, int pos) {
		if (pos == s.length())
			return;
		int next = node[index].next[s.charAt(pos) - 'a'];
		if (next == 0) {
			node[index].next[s.charAt(pos) - 'a'] = size;
			node[size++] = new Node();
			if (pos == s.length() - 1)
				node[size - 1].end = cur;
			else
				insert(size - 1, pos + 1);
		} else {
			if (pos == s.length() - 1)
				node[index].end = cur;
			else
				insert(next, pos + 1);
		}
	}
}